1. Field of the Invention
The present invention relates generally to the field of data encoding and particularly to encoding of motion picture video data.
2. Description of the Related Art
It is well known in the art to encode data in order to compress the data or to make the data less prone to errors during transmission or storage. Typically, these two objectives are seen as mutually exclusive, since making transmission of data less prone to errors usually involves adding error-correcting information to the data, whereas compression of the data involves eliminating redundant portions of the data. Huffman codes are variable length codes and have been considered excellent codes for compression of information. A necessary and sufficient condition to qualify a code as a Huffman code is that no individual code is identical to the initial bits of any other individual code. For example, if one code in a Huffman code is `11` then no other codes can start with `11`, codes such as `111`, `110`, `1111` and the like cannot be used.
Alternatively, Gray codes have been considered excellent codes for minimizing noise and therefore errors. Gray codes have the property that for each individual code in an enumerated sequence, both the next code in order and the previous code in order can be obtained by changing only one bit of the current code. These properties can result in fewer errors and less catastrophic errors because an error of a single bit is likely to result in a code for something close in sequence to the intended data. Gray codes are necessarily fixed-length codes.
In the area of transmission and encoding of motion picture video data, a well known standard is the MPEG (Motion Picture Experts Group) 4 standard, which describes a method for compressing motion picture video data for transmission. See MPEG-4, Coding of Moving Pictures and Audio, ISO/IEC JTC1 SC29 WG11. The MPEG-4 standard uses a variable length Huffman code to compress video data, thereby allowing large amounts of data to be transmitted in a short period of time. Also well known in the art is the JPEG (Joint Photographic Experts Group) standard for encoding of pictures. See ISO/IEC JTC1 SC29 WG1, JPEG, IS 10918/1. The JPEG standard provides a well known system for encoding pictures in a compressed format.
FIG. 1a shows a bit length chart for the MPEG-4 standard. Each box represents a motion vector that would be transmitted to indicate that a portion of a video image moved a direction and distance corresponding to the location of the box. The number in each box indicates how many bits are required to encode the motion vector corresponding to that location.
FIG. 1b shows a table of bit codes for the MPEG-4 standard. Each code corresponds to a certain distance along one of the two axes (either X or Y) available on a video screen. This code is generated as a Huffman code, so a high compression ratio to the original data has been achieved.
FIG. 1c shows a chart of the codes used for motion vectors in the MPEG-4 standard. Each box contains the code for a motion vector indicating motion in the direction of that box from the center box and proportional to that box's distance from the center box. These codes contain an X and Y component, each of variable length. The X and Y components can be read from the table of bit codes illustrated by FIG. 1b. For example, the code for the box one box above and one box to the right of the center box is `010 011` and `0110 011` is the code for the box two boxes above and one box to the left of the center box. Likewise, `11` is the code for the center box, representing zero boxes from the center in the X direction and zero boxes from the center in the Y direction.
FIG. 2 illustrates a 3 bit Gray code. As can be seen, the difference between any code in the table and the code adjacent to it, either above or below, involves a single bit transition. Also notable is that Gray codes are circular in nature, the last entry in the table `100` and the first entry in the table `000` involve only one bit transition.
As has been mentioned, one disadvantage of a Huffman code is that it is typically not robust. Likewise, one disadvantage of a Gray code is that it does not achieve much compression of data relative to other encoding methods. What is desired is a robust encoding method that still achieves high data compression.
In the case of MPEG-4, high compression is achieved, but robust encoding is not. Therefore, a more robust encoding method for MPEG-4 motion vectors is desirable, while maintaining a high level of data compression.